import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/5 10:19
 * @description 动态规划
 */
public class Solution {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
    }
    public int stoneGameII(int[] piles) {
        int len = piles.length, sum = 0;
        // dp[i][j] 表示剩余[i..len-1]堆石头，M = j的情况下，先取的人能获得的最多石头数
        int[][] dp = new int[len][len + 1];
        // 剩最后一堆时，一定有最佳方案，剩很多堆时不好算，要依赖后面的状态，所以从后往前递推
        for (int i = len - 1; i >= 0; i--) {
            sum += piles[i];
            for (int M = 1; M <= len; M++) {
                if (i + 2 * M >= len) {
                    // 剩下的堆能够全部取走
                    dp[i][M] = sum;
                } else {
                    // 不能取走，那就取最大，使得后手人利益最小
                    for (int x = 1; x <= 2 * M; x++) {
                        dp[i][M] = Math.max(dp[i][M], sum - dp[i + x][Math.max(M, x)]);
                    }
                }
            }
        }
        return dp[0][1];
    }
}
